package danran.regular;

import bishi.meituan.Solution;

import java.util.*;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;

/**
 * @Classname Simple
 * @Description TODO
 * @Date 2021/10/15 10:35
 * @Created by ASUS
 */
public class Simple {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        int start = -1, end = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                start = i;
                break;
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == target) {
                end = i;
                break;
            }
        }
        return new int[]{start, end};
    }

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (nums[mid] > target) {
                if (0 == mid) return 0;
                right = mid;
            } else if (nums[mid] < target) {
                if (mid == left) {
                    if (nums[right] >= target) return right;
                    else return right + 1;
                }
                left = mid;
            } else return mid;
        }
        return left;
    }

    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 1) return;
        Queue<Integer> q = new ArrayDeque<>();
        int length = matrix.length;
        for (int[] ints : matrix) {
            for (int j = 0; j < matrix.length; j++) {
                q.offer(ints[j]);
            }
        }
        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j < length; j++) {
                if (!q.isEmpty()) {
                    matrix[j][i] = q.poll();
                }
            }
        }
        System.out.println(Arrays.deepToString(matrix));
    }

    public int findLHS(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        int ans = 0;
        for (int num : nums) count.put(num, count.getOrDefault(num, 0) + 1);
        for (int k : count.keySet()) {
            int x = count.get(k);
            if (count.containsKey(k + 1)) ans = Math.max(ans, x + count.get(k + 1));
        }
        return ans;
    }

    static class SpiralOrder {
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 右下左上

        // f: 0->右，1=下，2=左，3=上
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> ans = new ArrayList<>();
            byte[][] visited = new byte[matrix.length][matrix[0].length];
            Queue<int[]> q = new ArrayDeque<>();
            q.offer(new int[]{0, 0, 0});
            int[] mid = {0, 0, 0};
            while (visited[mid[0]][mid[1]] == 0) {
                int x = mid[0], y = mid[1], f = mid[2] % 4;
                if (visited[x][y] == 0) {// not visited yet
                    ans.add(matrix[x][y]);
                    visited[x][y] = 1;
                    for (int i = f; i < f + 4; i++) {
                        int[] dir = dirs[i];
                        int dx = x + dir[0], dy = y + dir[1];
                        if (dx < 0 || dx == matrix.length
                                || dy < 0 || dy == matrix[0].length
                                || visited[dx][dy] == 1) {
                            continue;
                        } else {
                            q.offer(new int[]{dx, dy, i});
                            mid[0] = dx;
                            mid[1] = dy;
                            mid[2] = i;
                            break;
                        }
                    }
                }
            }
//            while (!q.isEmpty()) {
//                int[] cur = q.poll();
//                int x = cur[0], y = cur[1], f = cur[2] % 4;
//                if (visited[x][y] == 0) {// not visited yet
//                    ans.add(matrix[x][y]);
//                    visited[x][y] = 1;
//                    for (int i = f; i < f + 4; i++) {
//                        int[] dir = dirs[i];
//                        int dx = x + dir[0], dy = y + dir[1];
//                        if (dx < 0 || dx == matrix.length
//                                || dy < 0 || dy == matrix[0].length
//                                || visited[dx][dy] == 1) {
//                            continue;
//                        } else {
//                            q.offer(new int[]{dx, dy, i});
//                            break;
//                        }
//                    }
//                }
//            }
            System.out.println(ans);
            return ans;
        }

        public static void main(String[] args) {
            new SpiralOrder().spiralOrder(new int[][]{
                    {1, 2, 3, 4},
                    {5, 6, 7, 8},
                    {9, 10, 11, 12},
                    {13, 14, 15, 16}
            });
        }
    }

    static class TreeNode {
        public int val;
        public List<TreeNode> children;
        public TreeNode left, right;

        public TreeNode() {
        }

        public TreeNode(int _val) {
            val = _val;
        }

        public TreeNode(int _val, List<TreeNode> _children) {
            val = _val;
            children = _children;
        }
    }

    static class MaxDepth {


        public int maxDepth(TreeNode root) {
            int ans = 0;
            ans = dfs(root, ans);
            return ans;
        }

        private int dfs(TreeNode root, int ans) {
            if (root == null) return ans;
            ans++;
            int dep = 0;
            for (TreeNode child : root.children) {
                dep = Math.max(dfs(child, 0), dep);
            }
            return ans + dep;
        }
    }

    static class MergeIntervals {
        public int[][] merge(int[][] intervals) {
            if (intervals.length <= 1) return intervals;
            // 二维数组按照每个数组的第一个数升序排序
            Arrays.sort(intervals, Comparator.comparingInt(e -> e[0]));
            List<int[]> tmp_ans = new ArrayList<>();
            int[] cur = intervals[0], after;
            for (int i = 1; i < intervals.length; i++) {
                after = intervals[i];
                if (cur[1] < after[0]) {
                    tmp_ans.add(new int[]{cur[0], cur[1]});
                    cur = after;
                } else {
                    cur[0] = Math.min(cur[0], after[0]);
                    cur[1] = Math.max(cur[1], after[1]);
                }
            }
            tmp_ans.add(cur);
            return tmp_ans.toArray(new int[tmp_ans.size()][2]);
        }

        public int[][] insert(int[][] intervals, int[] newInterval) {
            List<int[]> t = new ArrayList<>(Arrays.asList(intervals));
            t.add(newInterval);
            return merge(t.toArray(new int[t.size()][2]));
        }

        public static void main(String[] args) {
            new MergeIntervals().merge(new int[][]{{1, 2}, {2, 6}, {8, 19}, {15, 18}});
        }
    }

    static class GenerateMatrix {
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 右下左上

        public int[][] generateMatrix(int n) {
            int[][] matrix = new int[n][n];
            helper(matrix);
            return matrix;
        }

        private void helper(int[][] matrix) {
            int cnt = 1;
            int[] q = new int[]{0, 0, 0};
            byte[][] v = new byte[matrix.length][matrix.length];
            while (v[q[0]][q[1]] == 0) {
                int x = q[0], y = q[1], f = q[2] % 4;
                if (v[x][y] == 0) {
                    v[x][y] = 1;
                    matrix[x][y] = cnt++;
                    for (int i = f; i < f + 4; i++) {
                        int dx = x + dirs[i][0], dy = y + dirs[i][1];
                        if (dx < 0 || dx == matrix.length || dy < 0 || dy == matrix.length || v[dx][dy] == 1) continue;
                        q[0] = dx;
                        q[1] = dy;
                        q[2] = i;
                        break;
                    }
                }
            }
        }

        public static void main(String[] args) {
            System.out.println(Arrays.deepToString(new GenerateMatrix().generateMatrix(4)));
        }
    }

    static class RotateRight {

        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || k == 0) return head;
            int cnt = 1;
            ListNode tail = head;
            while (tail.next != null) {
                tail = tail.next;
                cnt++;
            }
            tail.next = head;
            cnt = cnt - (k % cnt);
            System.out.println(cnt);
            for (int i = 0; i < cnt; i++) {
                tail = tail.next;
            }
            head = tail.next;
            tail.next = null;
            return head;
        }

        public int[] plusOne(int[] digits) {
            digits[digits.length - 1]++;
            for (int i = digits.length - 1; i > 0; i--) {
                if (digits[i] == 10) {
                    digits[i] = 0;
                    digits[i - 1]++;
                }
            }
            if (digits[0] == 10) {
                int[] ans = new int[digits.length + 1];
                ans[0] = 1;
                ans[1] = 0;
                System.arraycopy(digits, 1, ans, 2, digits.length - 1);
                return ans;
            }
            return digits;
        }

        public static void main(String[] args) {
            System.out.println(Arrays.toString(new RotateRight().plusOne(new int[]{9, 8, 9})));
        }
    }

    static class AddBinary {

        public String addBinary(String a, String b) {
            if (a.length() == 0 || a.equals("0")) return b;
            if (b.length() == 0 || b.equals("0")) return a;
            String t;
            if (a.length() < b.length()) {// swapping
                t = a;
                a = b;
                b = t;
            }
            int dif = a.length() - b.length();
            int c = 0;// 进位
            StringBuilder builder = new StringBuilder("0".repeat(a.length() + 1));
            for (int i = b.length() - 1; i >= 0; i--) {
                int sum = add(a.charAt(i + dif), b.charAt(i), c);
                c = sum / 2;
                builder.setCharAt(i + dif + 1, (char) ((sum % 2) + '0'));
            }
            for (int i = dif - 1; i >= 0; i--) {
                int sum = add(a.charAt(i), builder.charAt(i + 1), c);
                c = sum / 2;
                builder.setCharAt(i + 1, (char) ((sum % 2) + '0'));
            }
            if (c == 0) return builder.substring(1);
            builder.setCharAt(0, '1');
            return builder.toString();
        }

        public int add(char a, char b, int c) {
            return (a - '0') + (b - '0') + c;
        }

        public static void main(String[] args) {
            System.out.println(new AddBinary().addBinary("101", "1"));
        }
    }

    static class SetZero {
        public void setZeroes(int[][] matrix) {
            Set<Integer> row = new HashSet<>(), column = new HashSet<>();
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) {
                        row.add(i);
                        column.add(j);
                    }
                }
            }
            for (Integer r : row) {
                for (int i = 0; i < matrix[0].length; i++) {
                    matrix[r][i] = 0;
                }
            }
            for (Integer c : column) {
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][c] = 0;
                }
            }
        }
    }

    static class SearchMatrix {
        public boolean searchMatrix(int[][] matrix, int target) {
            int row = 0, f = 0;
            for (int i = 0; i < matrix.length - 1; i++) {
                if (matrix[i][0] == target || matrix[i + 1][0] == target) return true;
                if (matrix[i][0] < target && target < matrix[i + 1][0]) {
                    row = i;
                    f = 1;
                    break;
                }
            }
            if (matrix[matrix.length - 1][0] == target) return true;
            row = f == 0 ? matrix.length - 1 : row;
            System.out.println(row);
            for (int i = 0; i < matrix[0].length; i++) {
                if (matrix[row][i] == target) return true;
            }
            return false;
        }
    }

    static class BoardExit {
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        boolean found = false;

        public boolean exist(char[][] board, String word) {
            byte[][] v = new byte[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    dfs(board, word, v, i, j, 1);
                }
            }

            return found;
        }

        private void dfs(char[][] board, String word, byte[][] v, int x, int y, int level) {
            if (v[x][y] != 0 || found) return;
            if (board[x][y] == word.charAt(level - 1)) {
                if (level == word.length()) {
                    found = true;
                    return;
                }
                v[x][y] = 1;
                for (int[] dir : dirs) {
                    int dx = x + dir[0], dy = y + dir[1];
                    if (dx < 0 || dx == board.length || dy < 0 || dy == board[0].length || v[dx][dy] == 1) continue;
                    dfs(board, word, v, dx, dy, level + 1);
                }
                v[x][y] = 0;
            }
        }

        public static void main(String[] args) {
            System.out.println(new BoardExit().exist(new char[][]{
                    {'A', 'B', 'C', 'E'},
                    {'S', 'F', 'C', 'S'},
                    {'A', 'D', 'E', 'E'}
            }, "ABCB"));
        }
    }

    static class RemoveDuplicates {
        public int removeDuplicates(int[] nums) {
            int cnt = 0;
            Map<Integer, Integer> map = new HashMap<>();
            List<Integer> order = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if (!map.containsKey(nums[i])) order.add(nums[i]);
                map.put(nums[i], (cnt = map.getOrDefault(nums[i], 0)) == 2 ? 2 : cnt + 1);
            }
            cnt = 0;
            for (Integer value : map.values()) {
                cnt += value;
            }
            int idx = 0;
            for (Integer k : order) {
                for (int i = 0; i < map.get(k); i++) {
                    nums[idx++] = k;
                }
            }
            return cnt;
        }

        public int removeDuplicates_better(int[] nums) {
            int i = 0;
            for (int n : nums)
                if (i < 2 || n > nums[i - 2])
                    nums[i++] = n;
            return i;
        }

        /***
         * 执行结果：
         * 通过
         * 显示详情
         *
         * 添加备注
         * 执行用时：5 ms, 在所有 Java 提交中击败了13.73% 的用户
         * 内存消耗：37.8 MB, 在所有 Java 提交中击败了56.13% 的用户
         * 通过测试用例：166 / 166
         */
        public ListNode deleteDuplicates2(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode p = head;
            List<Integer> tmp = new ArrayList<>();
            Map<Integer, Integer> map = new HashMap<>();
            while (p != null) {
                if (!tmp.contains(p.val)) tmp.add(p.val);
                map.put(p.val, map.getOrDefault(p.val, 0) + 1);
                p = p.next;
            }
            head = new ListNode();
            p = head;
            for (Integer k : tmp) {
                if (map.get(k) == 1) {
                    p.next = new ListNode();
                    p = p.next;
                    p.val = k;
                }
            }
            return head.next;
        }

        public ListNode deleteDuplicates3(ListNode head) {
            // the list is empty or just has one element, return head directly.
            if (head == null || head.next == null) return head;
            // initialize a list or set to store the elements that have already in the linked list
            List<Integer> tmp = new ArrayList<>();
            while (head != null) {
                if (!tmp.contains(head.val)) tmp.add(head.val);
                head = head.next;
            }
            ListNode p = new ListNode();
            head = p;
            for (Integer item : tmp) {
                p.next = new ListNode(item);
                p = p.next;
            }
            return head.next;
        }

        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) {
                return null;
            }
            if (head.next == null) {
                return head;
            }
            if (head.val == head.next.val) {
                head = deleteDuplicates(head.next);
            } else {
                head.next = deleteDuplicates(head.next);
            }
            return head;
        }

        public ListNode partition(ListNode head, int x) {
            ListNode dx = new ListNode(), dy = new ListNode(), xp = dx, yp = dy;
            while (head != null) {
                if (head.val < x) {
                    xp.next = new ListNode(head.val);
                    xp = xp.next;
                } else {
                    yp.next = new ListNode(head.val);
                    yp = yp.next;
                }
                head = head.next;
            }
            xp.next = dy.next;
            return dx.next;
        }

        public void merge(int[] nums1, int m, int[] nums2, int n) {
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (int i = 0; i < m; i++) {
                queue.offer(nums1[i]);
            }
            for (int i = 0; i < n; i++) {
                queue.offer(nums2[i]);
            }
            int idx = 0;
            while (!queue.isEmpty()) nums1[idx++] = queue.poll();
            System.out.println(Arrays.toString(nums1));
        }

        public ListNode reverseBetween(ListNode head, int left, int right) {
            if (head == null || head.next == null || left == right) return head;
            left--;
            right--;
            int steps = right - left;
            ListNode a = head, b = head, c = head, d;
            for (int i = 0; i < steps; i++) {
                b = b.next;
            }
            for (int i = 0; i < left; i++) {
                a = a.next;
                b = b.next;
            }
            d = b.next;
            b.next = null;
            for (int i = 0; i < left - 1; i++) {
                c = c.next;
            }
            ListNode[] nodes = reverse(a);
            c.next = nodes[0];
            nodes[1].next = d;
            return left == 0 ? nodes[0] : head;
        }

        public ListNode[] reverse(ListNode head) {
            ListNode[] ans = new ListNode[2];
            if (head == null) return ans;
            if (head.next == null) {
                ans[1] = head;
                ans[0] = head;
                return ans;
            }
            Stack<ListNode> stack = new Stack<>();
            while (head != null) {
                stack.push(head);
                head = head.next;
            }
            ListNode dummy = new ListNode(), p = dummy;
            while (!stack.isEmpty()) {
                p.next = stack.pop();
                p.next.next = null;
                p = p.next;
            }
            ans[0] = dummy.next;
            ans[1] = p;
            return ans;
        }

        public boolean isPalindrome(String str) {
            str = str.trim().toLowerCase();
            System.out.println(str);
            char[] chars = str.toCharArray();
            int left = 0, right = chars.length - 1;
            while (left < right) {
                while (judge(chars[left])) left++;
                while (judge(chars[right])) right--;
                if (chars[left] == chars[right]) {
                    left++;
                    right--;
                } else {
                    return false;
                }
            }
            return true;
        }

        private boolean judge(char ch) {
            return !((ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9'));
        }

        public int singleNumber(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                if (!set.add(num)) set.remove(num);
            }
            return set.iterator().next();
        }

        public static void main(String[] args) {
            int[] array = {3, 2, 2, 1, 3};
            System.out.println(new RemoveDuplicates().singleNumber(array));
            ListNode head = new Simple().generateList(array);
            new Simple().printList(head);
            ListNode listNode = new RemoveDuplicates().reverseBetween(head, 2, 4);
            new Simple().printList(listNode);
        }
    }

    public ListNode generateList(int[] array) {
        ListNode head = new ListNode();
        ListNode p = head;
        for (int i = 0; i < array.length; i++) {
            p.val = array[i];
            if (i == array.length - 1) continue;
            p.next = new ListNode();
            p = p.next;
        }
        return head;
    }

    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() <= 10) return new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        String substring;
        for (int i = 0; i < s.length() - 9; i++) {
            substring = s.substring(i, i + 10);
            map.put(substring, map.getOrDefault(substring, 0) + 1);
        }
        System.out.println(map);
        return map.entrySet().stream().filter(e -> e.getValue() > 1).map(Map.Entry::getKey).collect(Collectors.toList());
    }

    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int len = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                len = len == 0 ? right - left + 1 : Math.min(len, right - left + 1);
                sum -= nums[left++];
            }
        }
        return len;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length <= 1 || k == 0) return false;
        int right = 1;
        for (int left = 0; left < nums.length - 1; ) {
            if (right == nums.length) {
                left++;
                right = left + 1;
            }
            if (nums[right] == nums[left]) return true;
            if (right - left == k) {
                left++;
                right = left + 1;
            } else right++;
        }
        return false;
    }

    public void printList(ListNode head) {
        if (head == null) System.out.println("[]");
        while (head != null) {
            System.out.print(head.val + "->");
            head = head.next;
        }
        System.out.println();
    }

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (val == root.val) return root;
        if (val < root.val) return searchBST(root.left, val);
        return searchBST(root.right, val);
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            Integer[] items = new Integer[i + 1];
            Arrays.fill(items, 1);
            ans.add(new ArrayList<>(Arrays.asList(items)));
        }
        if (numRows <= 2) return ans;
        List<Integer> cur, before;
        for (int i = 2; i < numRows; i++) {
            cur = ans.get(i);
            before = ans.get(i - 1);
            for (int j = 1; j < i; j++) {
                cur.set(j, before.get(j - 1) + before.get(j));
            }
        }
        return ans;
    }

    public List<Integer> getRow(int rowIndex) {
        return generate(rowIndex + 1).get(rowIndex);
    }


    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int[] ans = new int[2];
        PriorityQueue<Double> q = new PriorityQueue<>();
        Map<Double, int[]> map = new HashMap<>();
        for (int x = 0; x < arr.length - 1; x++) {
            for (int y = x + 1; y < arr.length; y++) {
                q.offer(arr[x] * 1.0 / arr[y]);
                map.put(arr[x] * 1.0 / arr[y], new int[]{arr[x], arr[y]});
            }
        }
        for (int i = 0; i < k - 1; i++) {
            System.out.println(q.poll());
        }
        return map.get(q.poll());
    }


    static class Robber {
        public int rob(int[] nums) {
            if (nums.length == 1) return nums[0];
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < nums.length; i++) {
                int notRob = dp[i - 1];
                int Rob = dp[i - 2] + nums[i];
                dp[i] = Math.max(notRob, Rob);
            }
            return dp[dp.length - 1];
        }

        public int rob2(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            } else if (nums.length == 2) {
                return Math.max(nums[0], nums[1]);
            } else {
                return Math.max(robRange(nums, 0, nums.length - 2),
                        robRange(nums, 1, nums.length - 1));
            }
        }

        private int robRange(int[] nums, int x, int y) {
            int len = y - x + 1;
            int[] dp = new int[len];
            dp[0] = nums[x];
            dp[1] = Math.max(nums[x], nums[x + 1]);
            for (int i = x + 2; i <= y; i++) {
                int dp_idx = i - x;
                int rob = dp[dp_idx - 2] + nums[i];
                int notRob = dp[dp_idx - 1];
                dp[dp_idx] = Math.max(rob, notRob);
            }
            return dp[dp.length - 1];

        }
    }


    /***
     * TODO: review this problem
     */
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }

    public int maxPower(String s) {
        // 滑动窗口
        if (s == null || "".equals(s)) return 0;
        if (s.length() == 1) return 1;
        int ans = 1;
        int left = 0, right = 1;
        while (right < s.length()) {
            if (s.charAt(left) == s.charAt(right)) {
                ans = Math.max(ans, right - left + 1);
            } else {
                left = right;
            }
            right++;
        }
        return ans;
    }

    //3-739
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        if (n == 2) return 91;
        int dp = 91;
        for (int i = 2; i < n; i++) {
            dp = countNumbersWithUniqueDigitsH(n) + dp;
        }
        return dp;
    }

    public int countNumbersWithUniqueDigitsH(int n) {
        int res = 81, t = 8;
        for (int i = 0; i < n - 2; i++) {
            res *= t--;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Simple().countNumbersWithUniqueDigits(3));
        TimeUnit unit = null;
        BlockingQueue workQueue = null;
        ThreadPoolExecutor executor = new ThreadPoolExecutor(1, 1,1 , unit, workQueue);
    }
}
